package algorithms.leaning.class13;

import common.bean.TreeNode;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 *
 * @author guichang
 * @date 2021/6/13
 */

@SuppressWarnings("all")
public class Code2_二叉树_最低公共祖先 {
    // 暴力方法：遍历树生成一张子->父关系表，遍历a的父节点放入set，再遍历b的父节点判断是否再set中存在，第一个存在的即是最低公共祖先

    public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode a, TreeNode b) {
        return process(head, a, b).ancestor;
    }

    /**
     * 1、ab在左树或者右树汇聚
     * 2、ab在node节点汇聚
     */
    private static Info process(TreeNode node, TreeNode a, TreeNode b) {
        if (node == null) {
            return new Info(false, false, null);
        }
        Info tl = process(node.left, a, b);
        Info tr = process(node.right, a, b);
        boolean findA = node == a || tl.findA || tr.findA;
        boolean findB = node == b || tl.findB || tr.findB;
        TreeNode ans = null;
        if (tl.ancestor != null) {
            ans = tl.ancestor;
        } else if (tr.ancestor != null) {
            ans = tr.ancestor;
        } else if (findA && findB) {
            ans = node;
        }

        return new Info(findA, findB, ans);
    }

    private static class Info {
        boolean findA; // 树上是否发现A
        boolean findB; // 树上是否发现B
        TreeNode ancestor; // 最低公共祖先

        public Info(boolean findA, boolean findB, TreeNode ancestor) {
            this.findA = findA;
            this.findB = findB;
            this.ancestor = ancestor;
        }
    }
}